The present invention relates generally to computer structure and method for processing three-dimensional (xe2x80x9c3-Dxe2x80x9d) computer graphics in a 3-D graphics processor. More particularly, the present invention is directed to a computer structure and method for performing setup operations in a tiled graphics pipeline architecture using unified primitive descriptors, post tile sorting setup, and tile relative x-values and screen relative y-values.
The art and science of three-dimensional (xe2x80x9c3-Dxe2x80x9d) computer graphics concerns the generation, or rendering, of two-dimensional (xe2x80x9c2-Dxe2x80x9d) images of 3-D objects for display or presentation onto a display device or monitor, such as a Cathode Ray Tube or a Liquid Crystal Display. The object may be a simple geometry primitive such as a point, a line segment, or a polygon. More complex objects can be rendered onto a display device by representing the objects with a series of connected planar polygons, such as, for example, by representing the objects as a series of connected planar triangles. All geometry primitives may eventually be described in terms of one vertex or a set of vertices, for example, coordinate (x, y, z) that defines a point, for example, the endpoint of a line segment, or a corner of a polygon.
To generate a data set for display as a 2-D projection representative of a 3-D primitive onto a computer monitor or other display device, the vertices of the primitive must be processed through a series of operations, or processing stages in a graphics rendering pipeline. A generic pipeline is merely a series of cascading processing units, or stages wherein the output from a prior stage, serves as the input for a subsequent stage. In the context of a graphics processor, these stages include, for example, per-vertex operations, primitive assembly operations, pixel operations, texture assembly operations, rasterization operations, and fragment operations.
The details of the various processing stages, except where otherwise noted, are not necessary to practice the present invention, and for that reason, will not be discussed in greater detail herein. A summary of the common processing stages in a conventional rendering pipeline can be found in the following standard reference: xe2x80x9cFundamentals of Three-dimensional Computer Graphicsxe2x80x9d, by Watt, Chapter 5: The Rendering Process, pages 97 to 113, published by Addison-Wesley Publishing Company, Reading, Mass., 1989, reprinted 1991, ISBN 0-201-15442-0, which is hereby incorporated by reference for background purposes only.
Very few conventional graphics pipelines have tiled architectures. A tiled architecture is a graphic pipeline architecture that associates image data, and in particular geometry primitives, with regions in a 2-D window, where the 2-D window is divided into multiple equally size regions. Tiled architectures are beneficial because they allow a graphics pipeline to efficiently operate on smaller amounts of image data. In other words, a tiled graphics pipeline architecture presents an opportunity to utilize specialized, higher performance graphics hardware into the graphic pipeline.
Those graphics pipelines that do have tiled architectures do not perform mid-pipeline sorting of the image data with respect to the regions of the 2-D window. Conventional graphics pipelines typically sort image data either, in software at the beginning of a graphics pipelines, before any image data transformations have taken place, or in hardware the very end of the graphics pipeline, after rendering the image into a 2-D grid of pixels.
Significant problems are presented by sorting image data at the very beginning of the graphics pipelines. For example, sorting image data at the very beginning of the graphics pipelines, typically involves dividing intersecting primitives into smaller primitives where the primitives intersect, and thereby, creating more vertices. It is necessary for each of these vertices to be transformed into an appropriate coordinate space. Typically this is done by subsequent stage of the graphics pipeline.
Vertex transformation is computationally intensive. Because none of these vertices have yet been transformed into an appropriate coordinate space, each of these vertices will need to be transformed by a subsequent vertex transformation stage of the graphics pipeline into the appropriate coordinates space. Coordinate spaces are known. As noted above, vertex transformation is computationally intensive. Increasing the number of vertices by subdividing primitives before transformation, slows down the already slow vertex transformation process.
Significant problems are also presented by spatially sorting image data at the end of a graphics pipeline (in hardware). For example, sorting image data at the end of a graphic pipeline typically slows image processing down, because such an implementation typically xe2x80x9ctexture mapsxe2x80x9d and rasterizes image data that will never be displayed. To illustrate this, consider the following example, where a first piece of geometry is spatially located behind a second piece of opaque geometry. In this illustration, the first piece of geometry is occluded by the second piece of opaque geometry. Therefore, the first piece of geometry will never be displayed.
To facilitate the removal of occluded primitives, an additional value (beyond color) is typically maintained for each bitmap pixel of an image. This additional value is typically known as a z-value (also known as a xe2x80x9cdepth valuexe2x80x9d). The z-value is a measure of the distance from the eyepoint to the point on the object represented by the pixel with which the z-value corresponds. Removing primitives or parts of primitives that are occluded by other geometry is beneficial because it optimizes a graphic pipeline by processing only those image data that will be visible. The process of removing hidden image data is called culling.
Those tiled graphics pipelines that do have tiled architectures do not perform culling operations. Because, as discussed in greater detail above, it is desirable to sort image data mid-pipeline, after image data coordinate transformations have taken place, and before the image data has been texture mapped and/or rasterized, it is also desirable to remove hidden pixels from the image data before the image data has been texture mapped and/or rasterized. Therefore, what is also needed is a tiled graphics pipeline architecture that performs not only, mid-pipeline sorting, but mid-pipeline culling.
In a tile based graphics pipeline architecture, it is desirable to provide a culling unit with accurate image data information on a tile relative basis. Such image data information includes, for example, providing the culling unit those vertices defining the intersection of a primitive with a tile""s edges. To accomplish this, the image data must be clipped to a tile. This information should be sent to the mid-pipeline culling unit. Therefore, because a mid-pipeline cull unit is novel and its input requirements are unique, what is also needed, is a structure and method for a mid-pipeline host file sorting setup unit for setting up image data information for the mid-pipeline culling unit.
It is desirable that the logic in a mid-pipeline culling unit in a tiled graphics pipeline architecture be as high performance and streamlined as possible. The logic in a culling unit can be optimized for high performance by reducing the number of branches in its logical operations. For example, conventional culling operations typically include logic, or algorithms to determine which of a primitive""s vertices lie within a tile, hereinafter referred to as a vertex/tile intersection algorithm. Conventional culling operations typically implement a number of different vertices/tile intersection algorithms to accomplish this, one algorithm for each primitive type.
A beneficial aspect of needing only one such algorithm to determine whether a line segment""s or a triangle""s vertices lie within a tile, as compared requiring two such algorithms (one for each primitive type), is that total number of branches in logic implementing such vertex/tile intersection algorithms are reduced. In other words, one set of algorithms/set of equations/set of hardware could be used to perform the vertex/tile intersection algorithm for a number of different primitive types. In light of this, it would be advantageous to have a procedure for representing different primitives, such as, for example, a line segment and a triangle, as a single primitive type, while still retaining each respective primitive type""s unique geometric information. In this manner, the logic in a mid-pipeline culling unit in a tiled graphics pipeline architecture could be streamlined.
Other stages of a graphics pipeline, besides a culling unit, could also benefit in a similar manner from a procedure for representing different primitives as a single primitive type, while still retaining each respective primitive type unique geometric information. For example, a processing stage that sets up information for a culling unit could also share a set of algorithms/set of equations/set of hardware for calculating different primitive information.
In conventional tile based graphics pipeline architectures, geometry primitive vertices, or x-coordinates and y-coordinates, are typically passed between pipeline stages in screen based coordinates. Typically x-coordinates and y-coordinates are represented as integers having a limited number of fractional bits (sub pixel bits).
Because it is desirable to architect a tile based graphics pipeline architecture to be as streamlined as possible, it would be beneficial to represent x-coordinates and y-coordinates in with a smaller number of bits to reduce the amount of data being sent to a subsequent stage of the graphics pipeline. Therefore, what is needed is a structure and method for representing x-coordinates and y-coordinates in a tile based graphics pipeline architecture, such the number of bits required to pass vertice information to subsequent stages of the graphics pipeline is reduced.
Heretofore, tile based graphics pipeline architectures have been limited by sorting image data either prior to the graphics pipeline or in hardware at the end of the graphics pipeline, no tile based graphics pipeline architecture culling units, no mid-pipeline post tile sorting setup units to support tile based culling operations, and larger vertices memory storage requirements.
The present invention overcomes the limitations of the state-of-the-art by providing structure and method in a tile based graphics pipeline architecture for: (a) a mid-pipeline post tile sorting setup unit that supplies a mid-pipeline cull unit with tile relative image data information; (b) a unified primitive descriptor language for representing triangles and line segments as quadrilaterals and thereby reducing logic branching requirements of a mid-pipeline culling unit; and, (c) representing each of a primitive""s vertices in tile relative y-values and screen relative x-values, and thereby reducing the number of bits that need to be passed to subsequent stages of the graphics pipeline accurately, and efficiently represent a primitive""s vertices.
In summary, a mid-pipeline setup unit is one processing stage of a tile based 3-D graphics pipeline. The mid-pipeline setup unit processes image data in preparation for a subsequent mid-pipeline culling unit. A mid-pipeline sorting unit, previous to the mid-pipeline setup unit has already sorted the image data with respect to multiple tiles comprising a 2-D window. The image data including vertices describing a primitive.
In particular, the mid-pipeline setup unit is adapted to determine a set of clipping points that identify an intersection of the primitive with the tile, and also adapted to compute a minimum depth value for that part of the primitive intersecting the tile.
In yet another embodiment of the present invention the primitives x-coordinates are screen based and the y-coordinates are tile based.
In yet another embodiment of the present invention, the mid-pipeline setup unit is adapted to represent line segments and triangles as rectangles. Both line segments and triangles in this embodiment are described with respective sets of four vertices. In the case of triangles, not all of the vertices are needed to describe the triangle, one vertice will be will be degenerate, or not described.